#include <vector>
#include <iostream>

using namespace std;

/*
走过 path 之后，一共可以走过的路径的条数
*/
int ways(vector<vector<int>> path) {
  // 1. 终结条件 - 递归停止的条件
  if (path.size() == 13) {
    // 每当 path 中有 13 个元素的时候，表示机器人已经走完了 12 步。
    // 这时，path 就表示一条可行的行进路线。
    return 1;
  }

  // 2. 递归过程 - 递归执行的过程
  // 机器人的每一个位置，都有 4 个可能的行进方向：上下左右
  vector<vector<int>> directions {
    {0, 1}, {1, 0}, {0, -1}, {-1, 0} 
  };

  int count = 0; // 记录答案

  // 遍历机器人可以走的每一个方向
  for (vector<int> d : directions) {
    // 当前进方向是 d 的时候，机器人的位置怎么计算呢？
    // d[0] + ??? - 机器人的上一个位置的 x - path 的最后一个元素[0]
    // d[1] + ??? - 机器人的上一个位置的 y - path 的最后一个元素[1]
    int lastX = path.back()[0];
    int lastY = path.back()[1];

    // 向 d 方向走一格
    vector<int> next = {d[0] + lastX, d[1] + lastY};

    // next 是一个合法的位置么？
    // next 已经包含在 path 里了，机器人已经走过这个位置了，next 不是一个合法的位置
    // 否则，next 就是合法的位置。
    if (find(path.begin(), path.end(), next) == path.end()) {
      // 没找到
      vector<vector<int>> copy_path = path;
      copy_path.push_back(next);

      // copy_path 就是包含 next 位置的新路径了。
      count += ways(copy_path);
    }
  }

  return count;
}


int main(int argc, char const *argv[])
{
  /* code */
  cout << ways({{0, 0}}) << endl;
  /*
  ways({{0, 0}})

  ways({{0,0}, {0, 1}}) +
  ways({{0,0}, {1, 0}}) +
  ways({{0,0}, {0, -1}}) +
  ways({{0,0}, {-1, 0}}) 
  */
  return 0;
}
